package cxydmmszl.chapter04.t059;

import java.util.Scanner;

/**
 * <li style="color: red;">Prob</li>
 * 机器人达到指定位置方法数
 * <li style="color: red;">Desc</li>
 * 假设有排成一行的 N 个位置，记为 1~N，开始时机器人在 M 位置，机器人可以往左或者往右走，
 * 如果机器人在 1 位置，那么下一步机器人只能走到 2 位置，如果机器人在N位置，那么下一步机器人只能走到 N-1 位置。
 * 规定机器人只能走 k 步，最终能来到 P 位置的方法有多少种。由于方案数可能比较大，所以答案需要对 1e9+7 取模。<br/><br/>
 * 输入描述：<br/>
 * 输出包括一行四个正整数N（2<=N<=5000）、M(1<=M<=N)、K(1<=K<=5000)、P(1<=P<=N)。<br/><br/>
 * 输出描述：<br/>
 * 输出一个整数，代表最终走到 P 的方法数对 10^9+7 取模后的值。
 * <li style="color: red;">Link</li> CD17
 *
 * @author habitplus
 * @since 2021-09-01 10:55
 */
public class Main {
    private static final int MOD = 1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int p = sc.nextInt();
        int steps = ways3(n, m, k, p);
        System.out.println(steps);
    }

    // 动态规划
    public static int ways2(int n, int m, int k, int p) {
        // 参数无效，直接返回
        if (n < 2 || k < 1 || m < 1 || m > n || p < 1 || p > n) {
            return 0;
        }
        // dp[i][j] : 走 i 步到达 j 位置的有效方法数
        // dp[0][m] = 1, dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
        int[][] dp = new int[k + 1][n + 1];
        dp[0][m] = 1;

        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                if (j == 1)         dp[i][j] = dp[i - 1][j + 1];
                else if (j == n)    dp[i][j] = dp[i - 1][j - 1];
                else                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
            }
        }

        return dp[k][p];
    }

    // 动态规划：空间优化
    public static int ways3(int n, int m, int k, int p) {
        // 参数无效，直接返回
        if (n < 2 || k < 1 || m < 1 || m > n || p < 1 || p > n) {
            return 0;
        }
        // dp[i][j] : 走 i 步到达 j 位置的有效方法数
        // dp[0][m] = 1, dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
        int[] dp = new int[n + 1];
        dp[m] = 1;
        int leftUp, t;
        for (int i = 1; i <= k; i++) {
            leftUp = dp[1];
            for (int j = 1; j <= n; j++) {
                t = dp[j];
                if (j == 1)         dp[j] = dp[j + 1];
                else if (j == n)    dp[j] = leftUp;
                else                dp[j] = (leftUp + dp[j + 1]) % MOD;
                leftUp = t;
            }
        }

        return dp[p];
    }

    // 递归过程（尝试过程）
    public static int ways1(int n, int start, int rest, int end) {
        // 参数无效，直接返回
        if (n < 2 || rest < 1 || start < 1 || start > n || end < 1 || end > n) {
            return 0;
        }

        // 总共有 n 个位置，从 start 出发，还剩 rest 步，返回最终能达到 end 的方法数
        return walk(n, start, rest, end);
    }

    // n : 所有位置，即 1-n
    // curPos : 当前所在位置
    // restSteps : 剩余可走的步数
    // destPos : 目标位置
    private static int walk(int n, int curPos, int restSteps, int destPost) {
        if (restSteps == 0) {
            // 找到了一种走法
            return curPos == destPost ? 1 : 0;
        }

        int steps = 0;
        // 还有步数可以走
        if (restSteps > 0) {
            // 往左走一步
            if (curPos - 1 > 0) steps += walk(n, curPos - 1, restSteps - 1, destPost);
            // 往右走一步
            if (curPos + 1 <= n)  steps += walk(n, curPos + 1, restSteps - 1, destPost);
        }
        return steps;
    }
}
